{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shifting Letters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shiftingLetters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字母移位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个由小写字母组成的字符串 <code>s</code>，和一个长度相同的整数数组 <code>shifts</code>。</p>\n",
    "\n",
    "<p>我们将字母表中的下一个字母称为原字母的 <em>移位</em>&nbsp;<code>shift()</code>&nbsp;（由于字母表是环绕的， <code>'z'</code>&nbsp;将会变成&nbsp;<code>'a'</code>）。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>shift('a') = 'b'<font color=\"#333333\"><font face=\"Helvetica Neue, Helvetica, Arial, sans-serif\"><span style=\"font-size:14px\"><span style=\"background-color:#ffffff\">,&nbsp;</span></span></font></font></code><code>shift('t') = 'u'</code>,&nbsp;以及&nbsp;<code>shift('z') = 'a'</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>对于每个&nbsp;<code>shifts[i] = x</code>&nbsp;， 我们会将 <code>s</code>&nbsp;中的前&nbsp;<code>i + 1</code>&nbsp;个字母移位&nbsp;<code>x</code>&nbsp;次。</p>\n",
    "\n",
    "<p>返回 <em>将所有这些移位都应用到 <code>s</code> 后最终得到的字符串</em> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\", shifts = [3,5,9]\n",
    "<strong>输出：</strong>\"rpl\"\n",
    "<strong>解释： </strong>\n",
    "我们以 \"abc\" 开始。\n",
    "将 S 中的第 1 个字母移位 3 次后，我们得到 \"dbc\"。\n",
    "再将 S 中的前 2 个字母移位 5 次后，我们得到 \"igc\"。\n",
    "最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 \"rpl\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aaa\", shifts = [1,2,3]\n",
    "<strong>输出:</strong> \"gfd\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;由小写英文字母组成</li>\n",
    "\t<li><code>shifts.length == s.length</code></li>\n",
    "\t<li><code>0 &lt;= shifts[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "<span style=\"display:block\"><span style=\"height:0px\"><span style=\"position:absolute\">​​​​​​</span></span></span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shifting-letters](https://leetcode.cn/problems/shifting-letters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shifting-letters](https://leetcode.cn/problems/shifting-letters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n[3,5,9]', '\"aaa\"\\n[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        s_len = len(s)\n",
    "        diff = [0]*(s_len+1)\n",
    "        for start, end, direction in shifts:\n",
    "            if direction:\n",
    "                diff[start]+=1\n",
    "                diff[end+1]-= 1\n",
    "            else:\n",
    "                diff[start]-=1\n",
    "                diff[end+1]+= 1\n",
    "        shifts_list = [ord(v)-97 for v in s]\n",
    "        # print(diff)\n",
    "        shifts_list[0] = (shifts_list[0]+diff[0])%26\n",
    "        for i in range(1, s_len):\n",
    "            diff[i]+=diff[i-1]\n",
    "            shifts_list[i] = (shifts_list[i]+diff[i])%26\n",
    "        return ''.join(chr(v+97) for v in shifts_list)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        prefix_array = [0] * (len(s)+1)\n",
    "        for start, end, direction in shifts:\n",
    "            counter = 1 if direction == 1 else -1\n",
    "            prefix_array[start]+=counter\n",
    "            prefix_array[end+1]-=counter\n",
    "\n",
    "        for i in range(1, len(prefix_array)):\n",
    "            prefix_array[i]+=prefix_array[i-1]\n",
    "\n",
    "        result = \"\"\n",
    "        for i in range(len(s)):\n",
    "            new_val = (ord(s[i]) + prefix_array[i]%26)\n",
    "            if 97 <= new_val <= 122:\n",
    "                result+=chr(new_val)\n",
    "            elif new_val > 122:\n",
    "                result+=chr(new_val%123 + 97)\n",
    "            else:\n",
    "                result+=chr(new_val+26)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        aord = ord(\"a\")\n",
    "        diffs = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            d = 1 if dir else -1\n",
    "            diffs[start] += d\n",
    "            diffs[end+1] -= d\n",
    "        \n",
    "        # cur = 0\n",
    "        # ans = [\"\"] * n\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     cur += diffs[i]\n",
    "        #     ans[i] = chr((ord(s[i]) - aord + cur) % 26 + aord)\n",
    "        # return \"\".join(ans)\n",
    "\n",
    "        return \"\".join(chr((ord(c) - aord + d) % 26 + aord) for c,d in zip(s, accumulate(diffs)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * (n+1)\n",
    "        for a,b,c in shifts:\n",
    "            num = 1 if c == 1 else -1\n",
    "            d[a] += num\n",
    "            d[b+1] -= num\n",
    "        sd = 0\n",
    "        ls = list(s)\n",
    "        for i,x,num in zip(range(n),ls,d):\n",
    "            sd += num\n",
    "            ls[i] = chr((ord(x)+sd-ord('a'))%26 + ord('a'))\n",
    "        return ''.join(ls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, val in shifts:\n",
    "            if val:\n",
    "                diff[start] += 1\n",
    "                diff[end+1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end+1] += 1\n",
    "        \n",
    "        s = list(s)\n",
    "        diff[0] = diff[0] - diff[0] // 26 * 26\n",
    "        s[0] = chr((ord(s[0]) - ord(\"a\") + 26 + diff[0]) % 26 + ord(\"a\"))\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i-1]\n",
    "            diff[i] = diff[i] - diff[i] // 26 * 26\n",
    "            s[i] = chr((ord(s[i]) - ord(\"a\") + 26 + diff[i]) % 26 + ord(\"a\"))\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff=[0]*(len(s)+1)\n",
    "        for i,j,r in shifts:\n",
    "            diff[i]+=2*r-1\n",
    "            diff[j+1]-=2*r-1\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            diff[i]+=diff[i-1]\n",
    "\n",
    "        res=[ord(_) for _ in s]\n",
    "        for i in range(len(res)):\n",
    "            cur=res[i]+diff[i]-ord('a')\n",
    "            res[i]=(cur+26)%26+ord('a')\n",
    "        return ''.join([chr(_) for _ in res])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0] * (n + 1)\n",
    "        for i, j, direct in shifts:\n",
    "            incdec[i] += direct * 2 - 1\n",
    "            incdec[j + 1] -= direct * 2 - 1\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] += 2 * i[2] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] -= 2 * i[2] - 1\n",
    "            if i[0] == 0: diff[0] += 2 * i[2] - 1\n",
    "            \n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        l = [ord(c) for c in s]\n",
    "        diff = [l[0]]\n",
    "\n",
    "        for i in range(len(l)):\n",
    "            if i < len(l) - 1:\n",
    "                diff.append(l[i + 1] - l[i])\n",
    "\n",
    "        diff.append(0)\n",
    "\n",
    "        for start, end, direction in shifts:\n",
    "            if direction == 1:\n",
    "                diff[start] += 1\n",
    "                diff[end + 1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end + 1] += 1\n",
    "\n",
    "        l = list(accumulate(diff))[: -1]\n",
    "        ret = ''.join([chr(97 + (n - 97) % 26) for n in l])\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n =len(s)\n",
    "        diff = [0] * n\n",
    "        for i,j,k in shifts:\n",
    "            diff[i] += (2 * k - 1)\n",
    "            if j + 1 < n:\n",
    "                diff[j + 1] += (-(2 * k - 1))\n",
    "\n",
    "        lst = [diff[0]]\n",
    "        for d in diff[1:]:\n",
    "            lst.append(lst[-1] + d)\n",
    "\n",
    "        ans = list()\n",
    "        for w in s:\n",
    "            ans.append(ord(w) - ord('a'))\n",
    "\n",
    "        word = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        for f in range(n):\n",
    "            ans[f] = word[(ans[f] + lst[f]) % 26]\n",
    "\n",
    "        return ''.join(each for each in ans)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0] * (n + 1)\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, src: str, shifts: List[List[int]]) -> str:\n",
    "        table = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        c2i = { c:i for i, c in enumerate(table) }\n",
    "        n = len(src)\n",
    "        diff = [0] * n\n",
    "        for s, e, d in shifts:\n",
    "            change = -1 if d == 0 else 1\n",
    "            diff[s] += change\n",
    "            if e + 1 < n:\n",
    "                diff[e+1] -= change\n",
    "        ans = [''] * n\n",
    "        add = 0\n",
    "        for i in range(n):\n",
    "            add += diff[i]\n",
    "            ci = c2i[src[i]] + add\n",
    "            nc = ((ci%26) + 26)%26\n",
    "            ans[i] = table[nc]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(self.c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, j, d in shifts:\n",
    "            diff[i] += d * 2 - 1\n",
    "            diff[j+1] -= d * 2 - 1\n",
    "        p = list(accumulate(diff))\n",
    "        return ''.join(chr((p[i] + ord(s[i]) - ord('a')) % 26 + ord('a')) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        res = [0] * len(s)\n",
    "        ans = \"\"\n",
    "        change = 0\n",
    "        for index,data in enumerate(zip(diff,s)):\n",
    "            i,char = data[0],data[1]\n",
    "            change += i\n",
    "            temp = change+ord(char)\n",
    "            while temp<97:\n",
    "                temp = 26 + temp\n",
    "            while temp>122:\n",
    "                temp = temp-26\n",
    "            res[index] = (temp)\n",
    "        char_list = [chr(i) for i in res]\n",
    "        result_string = ''.join(char_list)\n",
    "        # for i in res:\n",
    "        #     i = str(i)\n",
    "        #     ans+=i\n",
    "        return result_string\n",
    "\n",
    "\n",
    "        # #差分数组 转成ord 取余运算\n",
    "        # lis = [ord(i) for i in s]\n",
    "        # # diff = [l[0]] * len(l)\n",
    "        # ans = \"\"\n",
    "        # n = len(lis)\n",
    "        # diff =[lis[i]-lis[i-1] for i in range(1,n)]\n",
    "        # diff = [lis[0]] +diff \n",
    "        # for l,r,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[l] += 1\n",
    "        #         if r+1<n:\n",
    "        #             diff[r+1] -= 1\n",
    "        #     else:\n",
    "        #         diff[l] -= 1\n",
    "        #         if r+1 < n:\n",
    "        #             diff[r+1] += 1\n",
    "        #     while diff[0]<97:\n",
    "        #         diff[0] = 26 + diff[0]\n",
    "        #     while diff[0]>122:\n",
    "        #         diff[0] = diff[0]-26\n",
    "        # for i in range(1,n):\n",
    "        #     diff[i] += diff[i-1]     \n",
    "        #     while diff[i]<97:\n",
    "        #         diff[i] = 26 + diff[i]\n",
    "        #     while diff[i]>122:\n",
    "        #         diff[i] = diff[i]-26\n",
    "        #     # ans += chr(i)\n",
    "        #     # print(ans)\n",
    "        # for i in diff:\n",
    "        #     ans += chr(i)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        ans = [''] * len(s)\n",
    "        for i in range(len(shifts)):\n",
    "            diff[shifts[i][0]] += shifts[i][2] if shifts[i][2] == 1 else -1\n",
    "            diff[shifts[i][1] + 1] -= shifts[i][2] if shifts[i][2] == 1 else -1\n",
    "        for i, v in enumerate(accumulate(diff[:-1])):\n",
    "            ans[i] = chr(((ord(s[i]) + v) - 97) % 26 + 97)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        d = [0] * (len(s)+1)\n",
    "        for start,end,direction in shifts:\n",
    "            if direction == 1 :\n",
    "                d[start] +=1\n",
    "                d[end+1] -=1\n",
    "            elif direction == 0:\n",
    "                d[start]+=-1\n",
    "                d[end+1]-=-1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, j, d in shifts:\n",
    "            if d:\n",
    "                diff[i] += 1\n",
    "                diff[j+1] -= 1\n",
    "            else:\n",
    "                diff[i] -= 1\n",
    "                diff[j+1] += 1\n",
    "        p = list(accumulate(diff))\n",
    "        # print(p)\n",
    "        s = list(s)\n",
    "        for i in range(n):\n",
    "            # print(s[i], ord(s[i]))\n",
    "            s[i] = chr((p[i] + ord(s[i]) - ord('a')) % 26 + ord('a'))\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+2)\n",
    "        for f, t, x in shifts:\n",
    "            diff[f] += (-1) ** (x+1)\n",
    "            diff[t+1] -= (-1) ** (x+1)\n",
    "        return \"\".join(ascii_lowercase[(c2i[c]+x)%26] for c, x in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        \n",
    "        diff = [0 for _ in range(n)]\n",
    "        \n",
    "        for start, end, d in shifts:\n",
    "            d = 1 if d == 1 else -1\n",
    "            diff[start] += d\n",
    "            if end + 1< n:\n",
    "                diff[end + 1] -= d\n",
    "                \n",
    "        for i in range(1, n):\n",
    "            diff[i] += diff[i - 1]\n",
    "            \n",
    "        res = ['' for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            res[i] = chr(\n",
    "                (\n",
    "                    ord(s[i]) - ord('a') + diff[i] + 26\n",
    "                ) % 26 + ord('a')\n",
    "            )\n",
    "            \n",
    "        return ''.join(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff=[0]*(len(s)+1)\n",
    "        for start,end,dir in shifts:\n",
    "            dir=dir*2-1\n",
    "            diff[start]+=dir\n",
    "            diff[end+1]-=dir\n",
    "        t=[]\n",
    "        for c,shift in zip(s,accumulate(diff)):\n",
    "            t.append(ascii_lowercase[(c2i[c] + shift) % 26])    \n",
    "        return ''.join(t)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, val in shifts:\n",
    "            if val:\n",
    "                diff[start] += 1\n",
    "                diff[end+1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end+1] += 1\n",
    "        \n",
    "        s = list(s)\n",
    "        diff[0] = diff[0] - diff[0] // 26 * 26\n",
    "        s[0] = chr((ord(s[0]) - ord(\"a\") + 26 + diff[0]) % 26 + ord(\"a\"))\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i-1]\n",
    "            diff[i] = diff[i] - diff[i] // 26 * 26\n",
    "            s[i] = chr((ord(s[i]) - ord(\"a\") + 26 + diff[i]) % 26 + ord(\"a\"))\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0 for _ in range(n)]\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            if j + 1 < n:\n",
    "                incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        ans = [0]*26\n",
    "        for i in range(26):\n",
    "            ans[i] = chr(i+97)\n",
    "        dict = Counter()\n",
    "        res = list(s)\n",
    "        for st,end,flag in shifts:\n",
    "            if flag==1:\n",
    "                dict[st]+=1\n",
    "                dict[end+1]-=1\n",
    "            else:\n",
    "                dict[st]-=1\n",
    "                dict[end+1]+=1\n",
    "        m = 0\n",
    "        for i,x in enumerate(res):\n",
    "            m += dict[i]\n",
    "            t = ans[(ord(x)-97+m+26)%26]\n",
    "            res[i] = t\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for f, t, x in shifts:\n",
    "            diff[f] += (-1) ** (x+1)\n",
    "            diff[t+1] -= (-1) ** (x+1)\n",
    "        return \"\".join(ascii_lowercase[(c2i[c]+x)%26] for c, x in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        incdec = [0 for _ in range(n)]\n",
    "        for i, j, direct in shifts:\n",
    "            if direct == 0:\n",
    "                direct = -1\n",
    "            incdec[i] += direct\n",
    "            if j + 1 < n:\n",
    "                incdec[j + 1] -= direct\n",
    "        for i in range(1, n):\n",
    "            incdec[i] += incdec[i - 1]\n",
    "        \n",
    "        a = ord(\"a\")\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nc = chr((ord(s[i]) - a + incdec[i]) % 26 + a)\n",
    "            ans.append(nc)\n",
    "        return \"\".join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        aord = ord(\"a\")\n",
    "        diffs = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diffs[start] += dir*2 - 1\n",
    "            diffs[end+1] -= dir*2 - 1\n",
    "        \n",
    "        # cur = 0\n",
    "        # ans = [\"\"] * n\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     cur += diffs[i]\n",
    "        #     ans[i] = chr((ord(s[i]) - aord + cur) % 26 + aord)\n",
    "        # return \"\".join(ans)\n",
    "\n",
    "        return \"\".join(chr((ord(c) - aord + d) % 26 + aord) for c,d in zip(s, accumulate(diffs)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        temp = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        diff = [0] * len(s)\n",
    "        for a, b, c in shifts:\n",
    "            diff[a] += 2 * c - 1\n",
    "            if b + 1 <= len(s) - 1:\n",
    "                diff[b + 1] -= 2 * c - 1\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i] += diff[i-1]\n",
    "        ans = [None] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            ans[i] = temp[(ord(s[i]) - ord('a') + diff[i]) % 26]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] = diff[i[0]] + 1 if i[2] == 1 else diff[i[0]] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] = diff[i[1] + 1] - 1 if i[2] == 1 else diff[i[1] + 1] + 1\n",
    "            if i[0] == 0: diff[0] = diff[0] + 1 if i[2] == 1 else diff[0] - 1\n",
    "\n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import ascii_lowercase\n",
    "from itertools import accumulate\n",
    "c2i = {c:i for i,c in enumerate(ascii_lowercase)}\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]*(len(s)+1)\n",
    "        for start,end,dir in shifts:\n",
    "            diff[start] += 2*dir-1\n",
    "            diff[end+1] -= 2*dir-1\n",
    "        return ''.join(ascii_lowercase[(c2i[c]+shift)%26] for c,shift in zip(s,accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i) for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            while res[i]>122:\n",
    "                res[i]=97+res[i]-123\n",
    "            while res[i]<97:\n",
    "                res[i]=122-(96-res[i])\n",
    "            res[i]=chr(res[i])\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        import collections\n",
    "        arr = collections.defaultdict(int)\n",
    "        for start, end, count in shifts:\n",
    "            if count == 1:\n",
    "                arr[start] += 1\n",
    "                arr[end+1] -= 1\n",
    "            elif count == 0:\n",
    "                arr[start] -= 1\n",
    "                arr[end+1] += 1\n",
    "        tmp = 0\n",
    "        res = ''\n",
    "        for i in range(0, len(s)):\n",
    "            if i in arr:\n",
    "                tmp += arr[i]\n",
    "            res += chr(((ord(s[i])-ord('a'))+tmp)%26+ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法,利用取模优化时间复杂度。\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0]\n",
    "        n = len(s)\n",
    "        for i in range(1, n):\n",
    "            diff.append(ord(s[i]) - ord(s[i - 1]))\n",
    "\n",
    "        for i in shifts:\n",
    "            if i[0] > 0: diff[i[0]] = diff[i[0]] + 1 if i[2] == 1 else diff[i[0]] - 1\n",
    "            if i[1] < n - 1: diff[i[1] + 1] = diff[i[1] + 1] - 1 if i[2] == 1 else diff[i[1] + 1] + 1\n",
    "            if i[0] == 0: diff[0] = diff[0] + 1 if i[2] == 1 else diff[0] - 1\n",
    "\n",
    "        ans = [ord(s[0]) + diff[0]]\n",
    "        for i in range(1, n):\n",
    "            ans.append(ans[i - 1] + diff[i])\n",
    "        return ''.join(chr(97 + (i - 97) % 26) for i in ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * n\n",
    "        for ss, e, d in shifts:\n",
    "            diff[ss] += (1 if d == 1 else -1)\n",
    "            if e+1 < n:\n",
    "                diff[e+1] -= (1 if d == 1 else -1)\n",
    "\n",
    "        d = list(accumulate(diff))\n",
    "\n",
    "        alpha = {}\n",
    "        alpha2 = {}\n",
    "        for i in range(26):\n",
    "            alpha[chr(97+i)] = i\n",
    "            alpha[i] = chr(97+i)\n",
    "        \n",
    "            alpha2[chr(97+i)] = 25 - i\n",
    "            alpha2[25 - i] = chr(97+i)\n",
    "\n",
    "\n",
    "        ans = [0] * n\n",
    "\n",
    "        for i, ss in enumerate(s):\n",
    "            if d[i] >= 0:\n",
    "                new_ss = (alpha[ss] + d[i] % 26) % 26\n",
    "                new_ss = alpha[new_ss]\n",
    "            else:\n",
    "                new_ss = (alpha2[ss] + (-d[i]) % 26) % 26\n",
    "                new_ss = alpha2[new_ss]\n",
    "\n",
    "            ans[i] = new_ss\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        return ''.join(ascii_lowercase[(c2i[c] + shift) % 26] for c, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n+1)\n",
    "        for l, r, d in shifts:\n",
    "            d = d*2-1\n",
    "            diff[l] += d\n",
    "            diff[r+1] -= d\n",
    "        \n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            ans += chr((ord(s[i]) - 97 + diff[i]) % 26 + 97)\n",
    "            diff[i+1] += diff[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * n\n",
    "        for start, end, direction in shifts:\n",
    "            if direction:\n",
    "                d[start] += 1\n",
    "                if end + 1 < n:\n",
    "                    d[end + 1] -= 1\n",
    "            else:\n",
    "                d[start] -= 1\n",
    "                if end + 1 < n:\n",
    "                    d[end + 1] += 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            d[i] += d[i - 1]\n",
    "        \n",
    "        newstr = []\n",
    "        for i in range(n):\n",
    "            newstr.append(\n",
    "                chr\n",
    "                (\n",
    "                    (ord(s[i]) - ord('a') + d[i] + 26) % 26 + ord('a')\n",
    "                )\n",
    "            )\n",
    "        return ''.join(newstr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n+1)\n",
    "        for shift in shifts:\n",
    "            a = shift[0]\n",
    "            b = shift[1]\n",
    "            dir = shift[2]\n",
    "            delta = 1 if dir == 1 else -1\n",
    "            diff[a] += delta\n",
    "            diff[b+1] -= delta\n",
    "        \n",
    "        cur = 0\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            cur += diff[i]\n",
    "            new_char = (ord(s[i]) - ord('a') + cur) % 26\n",
    "            res.append(chr(new_char + ord('a')))\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s)+1)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += dir * 2 - 1\n",
    "            diff[end + 1] -= dir * 2 - 1\n",
    "        res = []\n",
    "        ans = \"\"\n",
    "        change = 0\n",
    "        for i,char in zip(diff,s):\n",
    "            change += i\n",
    "            temp = change+ord(char)\n",
    "            while temp<97:\n",
    "                temp = 26 + temp\n",
    "            while temp>122:\n",
    "                temp = temp-26\n",
    "            res.append(temp)\n",
    "        char_list = [chr(i) for i in res]\n",
    "        result_string = ''.join(char_list)\n",
    "        # for i in res:\n",
    "        #     i = str(i)\n",
    "        #     ans+=i\n",
    "        return result_string\n",
    "\n",
    "\n",
    "        # #差分数组 转成ord 取余运算\n",
    "        # lis = [ord(i) for i in s]\n",
    "        # # diff = [l[0]] * len(l)\n",
    "        # ans = \"\"\n",
    "        # n = len(lis)\n",
    "        # diff =[lis[i]-lis[i-1] for i in range(1,n)]\n",
    "        # diff = [lis[0]] +diff \n",
    "        # for l,r,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[l] += 1\n",
    "        #         if r+1<n:\n",
    "        #             diff[r+1] -= 1\n",
    "        #     else:\n",
    "        #         diff[l] -= 1\n",
    "        #         if r+1 < n:\n",
    "        #             diff[r+1] += 1\n",
    "        #     while diff[0]<97:\n",
    "        #         diff[0] = 26 + diff[0]\n",
    "        #     while diff[0]>122:\n",
    "        #         diff[0] = diff[0]-26\n",
    "        # for i in range(1,n):\n",
    "        #     diff[i] += diff[i-1]     \n",
    "        #     while diff[i]<97:\n",
    "        #         diff[i] = 26 + diff[i]\n",
    "        #     while diff[i]>122:\n",
    "        #         diff[i] = diff[i]-26\n",
    "        #     # ans += chr(i)\n",
    "        #     # print(ans)\n",
    "        # for i in diff:\n",
    "        #     ans += chr(i)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for start, end, direction in shifts:\n",
    "            if direction == 1:\n",
    "                diff[start] += 1\n",
    "                diff[end + 1] -= 1\n",
    "            else:\n",
    "                diff[start] -= 1\n",
    "                diff[end + 1] += 1\n",
    "\n",
    "        ans = ''\n",
    "        cumsum = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            cumsum += diff[i]\n",
    "            ans += chr(((ord(ch) - 97 + cumsum) % 26) + 97)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        shifts.sort()\n",
    "        pos = 0\n",
    "        n = len(s)\n",
    "        m = len(shifts)\n",
    "\n",
    "        ud = [0] * (n + 1)\n",
    "\n",
    "        cost = 0\n",
    "        ret = \"\"\n",
    "        for i in range(n):\n",
    "            while pos < m and shifts[pos][0] <= i:\n",
    "                if shifts[pos][2] == 0:\n",
    "                    ud[shifts[pos][1] + 1] += 1\n",
    "                    cost -= 1\n",
    "                else:\n",
    "                    ud[shifts[pos][1] + 1] -= 1\n",
    "                    cost += 1\n",
    "                pos += 1\n",
    "            cost += ud[i]\n",
    "            ret += chr(ord('a') + (ord(s[i]) - ord('a') + cost) % 26)\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        flag = [0]*(n+1)\n",
    "        for a,b,d in shifts:\n",
    "            if d==0:\n",
    "                flag[a]-=1\n",
    "                flag[b+1]+=1\n",
    "            else:\n",
    "                flag[a]+=1\n",
    "                flag[b+1]-=1\n",
    "        for i in range(1,n+1):\n",
    "            flag[i]+=flag[i-1]\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            nxt = flag[i] % 26\n",
    "            res += chr((ord(s[i])-ord('a') + nxt)%26 + ord('a'))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        d=[0]*(n+1)\n",
    "        for i in range(len(shifts)):\n",
    "            if shifts[i][2]==1:\n",
    "                d[shifts[i][0]]+=1\n",
    "                d[shifts[i][1]+1]-=1\n",
    "            else:\n",
    "                d[shifts[i][0]]-=1\n",
    "                d[shifts[i][1]+1]+=1\n",
    "        cur=0\n",
    "        ret=''\n",
    "        for i in range(n):\n",
    "            cur+=d[i]\n",
    "            ch=cur+ord(s[i])-ord('a')\n",
    "            if ch>=26:\n",
    "                ret+=chr(ch%26+ord('a'))\n",
    "            elif ch<0:\n",
    "                if ch%(-26)!=0:\n",
    "                    ret+=chr(26+ch%(-26)+ord('a'))\n",
    "                else:\n",
    "                    ret+='a'\n",
    "            else:\n",
    "                ret+=chr(ch+ord('a'))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        dif = [0] * (len(s) + 1)\n",
    "        for a, b, c in shifts:\n",
    "            d = 1 if c == 1 else -1\n",
    "            dif[a] += d\n",
    "            dif[b + 1] -= d\n",
    "        ans, p = \"\", 0\n",
    "        for i, c in enumerate(s):\n",
    "            p += dif[i]\n",
    "            ans += chr((ord(c) - ord('a') + p) % 26 + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        pos = [0] * len(s)\n",
    "\n",
    "        for (start, end, shift) in shifts:\n",
    "            pos[start] += 1 if shift == 1 else -1\n",
    "            if end+1 < len(s):\n",
    "                pos[end+1] -= 1 if shift == 1 else -1\n",
    "        \n",
    "        preSum = 0\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            preSum += pos[i]\n",
    "            # print(preSum, (ord(s[i]) + preSum - ord('a')) % 26)\n",
    "            res += chr(ord('a') + (ord(s[i]) + preSum - ord('a')) % 26)\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n)\n",
    "        for start, end, dir in shifts:\n",
    "            diff[start] += 1 if dir == 1 else -1\n",
    "            if end + 1 < n:\n",
    "                diff[end+1] -= 1 if dir == 1 else -1\n",
    "\n",
    "        ans = [[''] for _ in range(n)]\n",
    "        diff = list(accumulate(diff))\n",
    "        # for i in range(1, n):\n",
    "            # diff[i] += diff[i - 1]\n",
    "\n",
    "        ans = list(chr((ord(s[i]) - ord('a') + diff[i]) % 26 + ord('a')) for i in range(n))\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        c2i = {c: i for i, c in enumerate(ascii_lowercase)}\n",
    "        diff = [0] * (len(s) + 1)\n",
    "        for left, right, offset in shifts:\n",
    "            diff[left] += offset * 2 - 1\n",
    "            diff[right + 1] -= offset * 2 - 1\n",
    "        \n",
    "        return ''.join(ascii_lowercase[(c2i[i] + shift) % 26] for i, shift in zip(s, accumulate(diff)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 一维差分数组\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        for shift in shifts:\n",
    "            if shift[2] == 1:\n",
    "                dp[shift[0] + 1] += 1\n",
    "                if shift[1] + 1 < n:\n",
    "                    dp[shift[1] + 2] -= 1\n",
    "            else:\n",
    "                dp[shift[0] + 1] -= 1\n",
    "                if shift[1] + 1 < n:\n",
    "                    dp[shift[1] + 2] += 1\n",
    "        for _ in range(1, n+1):\n",
    "            dp[_] += dp[_ - 1]\n",
    "        res = ''\n",
    "        for i in range(n):\n",
    "            res += chr((ord(s[i]) - ord('a') + dp[i + 1]) % 26 + ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(s)\n",
    "        diff=[0]*(n+1)\n",
    "        for start,end,direct in shifts:\n",
    "            if direct==1:\n",
    "                diff[start]+=1\n",
    "                diff[end+1]-=1\n",
    "            else:\n",
    "                diff[start]-=1\n",
    "                diff[end+1]+=1\n",
    "        ans=\"\"\n",
    "        #print(diff)\n",
    "        nums=[x for x in accumulate(diff)]\n",
    "        #print(nums[:-1])\n",
    "        alph='abcdefghijklmnopqrstuvwxyz'\n",
    "        for i in range(n):\n",
    "            index=alph.index(s[i])+nums[i]\n",
    "            print(index)\n",
    "            ans+=alph[index%26]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        #一眼差分数组解法\n",
    "        n=len(s)\n",
    "        arr=[ord(i)-97 for i in s]\n",
    "        diff=[arr[0]]\n",
    "        for i in range(1,n):\n",
    "            diff.append(arr[i]-arr[i-1])\n",
    "        for l,r,d in shifts:\n",
    "            if d:\n",
    "                diff[l]+=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]-=1\n",
    "            else:\n",
    "                diff[l]-=1\n",
    "                if r+1==n: continue\n",
    "                diff[r+1]+=1\n",
    "        res=list(accumulate(diff))\n",
    "        for i in range(n):\n",
    "            res[i]%=26\n",
    "            res[i]=chr(res[i]+97)\n",
    "        print(res)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, s):\n",
    "        self.ori_s = s\n",
    "        self.real_size = len(s)\n",
    "        i = 0\n",
    "        while (1 << i) < self.real_size:\n",
    "            i += 1\n",
    "        \n",
    "        self.space_size = 1 << (i + 1)\n",
    "        self.leave_size = 1 << i\n",
    "\n",
    "        self.update_flag = [False] * self.space_size\n",
    "        self.update_info = [0] * self.space_size\n",
    "        self.cur_info = [0] * self.space_size\n",
    "\n",
    "        for i in range(self.real_size):\n",
    "            self.init(i, i, 0, self.leave_size - 1, 0)\n",
    "    \n",
    "    def init(self, lidx1, ridx1, lidx2, ridx2, idx):\n",
    "        if lidx2 == ridx2:\n",
    "            self.cur_info[idx] = ord(self.ori_s[lidx1]) - ord('a')\n",
    "            return\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        if midx2 < lidx1:\n",
    "            self.init(lidx1, ridx1, midx2 + 1, ridx2, ridx)\n",
    "        else:\n",
    "            self.init(lidx1, ridx1, lidx2, midx2, lidx)\n",
    "        \n",
    "        self.cur_info[idx] += ord(self.ori_s[lidx1]) - ord('a')\n",
    "    \n",
    "    def update(self, lidx1, ridx1, lidx2, ridx2, idx, val):\n",
    "        if lidx2 >= lidx1 and ridx2 <= ridx1:\n",
    "            self.cur_info[idx] += (val * (ridx2 - lidx2 + 1))\n",
    "            self.update_flag[idx] = True\n",
    "            self.update_info[idx] += val\n",
    "            if self.update_info[idx] == 0:\n",
    "                self.update_flag[idx] = False\n",
    "            return\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        \n",
    "        self.modify(lidx2, ridx2, idx)\n",
    "        if lidx1 <= midx2:\n",
    "            # self.modify(lidx2, midx2, lidx)\n",
    "            self.update(lidx1, ridx1, lidx2, midx2, lidx, val)\n",
    "        \n",
    "        if ridx1 > midx2:\n",
    "            # self.modify(midx2 + 1, ridx2, ridx)\n",
    "            self.update(lidx1, ridx1, midx2 + 1, ridx2, ridx, val)\n",
    "\n",
    "        self.cur_info[idx] = self.cur_info[lidx] + self.cur_info[ridx]\n",
    "    \n",
    "    def modify(self, lidx2, ridx2, idx):\n",
    "        if not self.update_flag[idx]:\n",
    "            return\n",
    "\n",
    "        val = self.update_info[idx]\n",
    "        self.update_flag[idx] = False\n",
    "        self.update_info[idx] = 0\n",
    "        # if val == 0:\n",
    "        #     return \n",
    "\n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "\n",
    "        self.cur_info[lidx] += (val * (midx2 - lidx2 + 1))\n",
    "        self.update_flag[lidx] = True\n",
    "        self.update_info[lidx] += val\n",
    "        self.cur_info[ridx] += (val * (ridx2 - midx2))\n",
    "        self.update_flag[ridx] = True\n",
    "        self.update_info[ridx] += val\n",
    "    \n",
    "    def get(self, lidx1, ridx1, lidx2, ridx2, idx):\n",
    "        if lidx2 >= lidx1 and ridx2 <= ridx1:\n",
    "            return self.cur_info[idx]\n",
    "        \n",
    "        midx2 = (lidx2 + ridx2) >> 1\n",
    "        lidx = (idx << 1) | 1\n",
    "        ridx = lidx + 1\n",
    "        \n",
    "        self.modify(lidx2, ridx2, idx)\n",
    "        res = 0\n",
    "        if lidx1 <= midx2:\n",
    "            res += self.get(lidx1, ridx1, lidx2, midx2, lidx)\n",
    "        \n",
    "        if ridx1 > midx2:\n",
    "            res += self.get(lidx1, ridx1, midx2 + 1, ridx2, ridx)\n",
    "\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 并查集  错，应该是线段树(Segment Tree)\n",
    "        st = SegmentTree(s)\n",
    "        # print(st.cur_info)\n",
    "\n",
    "        for i in range(len(shifts)):\n",
    "            st.update(shifts[i][0], shifts[i][1], 0, st.leave_size - 1, 0, 1 if shifts[i][2] == 1 else -1)\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            res.append(st.get(i, i, 0, st.leave_size - 1, 0))\n",
    "        \n",
    "        # print(st.cur_info)\n",
    "        # print(res)\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            res[i] = chr((97 + res[i] % 26))\n",
    "\n",
    "\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * (n+1)\n",
    "        for l,r,c in shifts:\n",
    "            d[l] += c * 2 - 1\n",
    "            d[r+1] -= c * 2 - 1\n",
    "        t = \"\"\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            c += d[i]\n",
    "            t += chr((ord(s[i]) - 97 + c + 26) % 26 + 97)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        diff = [0] * len(s)\n",
    "        \n",
    "        for start, end, direction in shifts:\n",
    "            action = 1 if direction == 1 else -1\n",
    "\n",
    "            diff[start] += action\n",
    "            if end + 1 < len(s):\n",
    "                diff[end + 1] -= action\n",
    "        for i in range(1, len(s)):\n",
    "            diff[i] += diff[i - 1]\n",
    "\n",
    "\n",
    "        return self._shift_string(s, diff)\n",
    "\n",
    "    def _shift_string(self, old_string: str, actions: List[int]) -> str:\n",
    "        results = \"\"\n",
    "        for s, m in zip(old_string, actions):\n",
    "            s2int = ord(s) - ord('a')\n",
    "            s2int = (s2int + m) % 26 + ord('a')\n",
    "            results += chr(s2int)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        dif = [0] * (len(s) + 1)\n",
    "        for a, b, c in shifts:\n",
    "            d = 1 if c == 1 else -1\n",
    "            dif[a] += d\n",
    "            dif[b + 1] -= d\n",
    "        ans, p = \"\", 0\n",
    "        for i, c in enumerate(s):\n",
    "            p += dif[i]\n",
    "            ans += chr((ord(c) - ord('a') + p) % 26 + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, sh: List[List[int]]) -> str:\n",
    "        n=len(ss)\n",
    "        f=[0]*(n+1)\n",
    "        for s,e,d in sh:\n",
    "            if d==1:\n",
    "                f[s]+=1\n",
    "                f[e+1]-=1\n",
    "            else:\n",
    "                f[s]-=1\n",
    "                f[e+1]+=1\n",
    "        for i in range(1,n):\n",
    "            f[i]+=f[i-1]\n",
    "        res=\"\"\n",
    "        for c,k in zip(ss,f):\n",
    "            k%=26\n",
    "            c=ord(c)+k\n",
    "            if c>ord(\"z\"):\n",
    "                c-=26\n",
    "            res+=chr(c)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        chafen = [0]*len(s)\n",
    "        for i in shifts:\n",
    "            left = i[0]\n",
    "            right = i[1]\n",
    "            # 向前移位定义为-1\n",
    "            if i[2] == 0:\n",
    "                chafen[left] -= 1\n",
    "                if right+1 < len(s):\n",
    "                    chafen[right+1] +=1\n",
    "            # 向后移位定义+1\n",
    "            if i[2] == 1:\n",
    "                chafen[left] += 1\n",
    "                if right+1 < len(s):\n",
    "                    chafen[right+1] -= 1\n",
    "        for i in range(1,len(s)):\n",
    "            chafen[i] += chafen[i-1]\n",
    "        # 字母开始移位操作\n",
    "        res = ''\n",
    "        for i in range(len(s)):\n",
    "            if chafen[i] < 0:\n",
    "                ind = ord(s[i]) - ord('a') + 26 +chafen[i]%26\n",
    "                ind = ind%26\n",
    "                res += chr(ind+ord('a'))\n",
    "\n",
    "            if chafen[i] > 0:\n",
    "                ind = ord(s[i])- ord('a') + chafen[i]%26\n",
    "                res += chr(ind%26+ord('a'))\n",
    " \n",
    "            if chafen[i] == 0:\n",
    "                res += s[i]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, shifts: List[List[int]]) -> str:\n",
    "        n=len(ss)\n",
    "        d=[0]*(n+1)\n",
    "        for s,e,dire in shifts:\n",
    "            d[s]+=1 if dire==1 else -1\n",
    "            d[e+1]-=1 if dire==1 else -1\n",
    "        move=[i for i in accumulate(d)]\n",
    "        ans=''\n",
    "        for i,x in enumerate(move[:n]):\n",
    "            t=(ord(ss[i])-ord('a')+x)%26+ord('a')\n",
    "            ans+=chr(t)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, ss: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(ss)\n",
    "        \n",
    "        diff = [0]*n\n",
    "        for s, e, d in shifts:\n",
    "            x = 1 if d else -1\n",
    "            diff[s] += x\n",
    "            if e+1<n:\n",
    "                diff[e+1] -= x\n",
    "        for i in range(1, n):\n",
    "            diff[i] += diff[i-1]\n",
    "        \n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            ans += chr((diff[i]+ord(ss[i])-ord(\"a\"))%26+ord(\"a\"))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s) \n",
    "        diff = [0]*n\n",
    "        for x,y,flag in shifts:\n",
    "            if flag == 1:    \n",
    "                diff[x] += 1\n",
    "                if y+1<n:\n",
    "                    diff[y+1] -=1\n",
    "            else:\n",
    "                diff[x] -= 1\n",
    "                if y+1<n:\n",
    "                    diff[y+1]+=1\n",
    "        d = 0\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            d += diff[i]\n",
    "            c = s[i]\n",
    "            ans += chr((ord(c)-ord('a')+d)%26+ord('a'))\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(s)\n",
    "        # diff = [0] *n\n",
    "        # for a,b,v in shifts:\n",
    "        #     if v == 1:\n",
    "        #         diff[a] += 1\n",
    "        #         if b+1<n:\n",
    "        #             diff[b+1] -= 1\n",
    "        #     elif v == 0:\n",
    "        #         diff[a] -= 1\n",
    "        #         if b+1<n:\n",
    "        #             diff[b+1] += 1\n",
    "        # # for i in range(1,n): #直接更新diff\n",
    "        # #     diff[i] = diff[i]+diff[i-1]\n",
    "        # res = ['']*n\n",
    "        # for i in range(n):\n",
    "        #     if i>0:\n",
    "        #         diff[i] = diff[i] + diff[i-1]\n",
    "        #     res[i] = chr((ord(s[i])-ord('a')+diff[i])%26 + ord('a'))\n",
    "        # # print(diff)\n",
    "        # return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        n = len(s)\n",
    "        diff = [0] * (n + 1)\n",
    "        for x, y, op in shifts:\n",
    "            if op:\n",
    "                diff[x] += 1\n",
    "                diff[y + 1] -= 1\n",
    "            else:\n",
    "                diff[x] += -1\n",
    "                diff[y + 1] -= -1\n",
    "            # print(diff)\n",
    "        total = 0\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            total += diff[i]\n",
    "            val = (ord(s[i]) - 97 + total + 26) % 26 + 97\n",
    "            # print(val)\n",
    "            c = chr(val)\n",
    "            ans += c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        f = [0] * (len(s) + 1)\n",
    "        for start, end, sign in shifts:\n",
    "            if sign == 1:\n",
    "                f[start] += 1\n",
    "                f[end + 1] -= 1\n",
    "            else:\n",
    "                f[start] += -1\n",
    "                f[end + 1] -= -1\n",
    "        res = ''\n",
    "        for i, n in enumerate(list(accumulate(f))[:-1]):\n",
    "            res += chr((n + ord(s[i]) - 97) % 26 + 97)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:\n",
    "        # 感觉是不是看到这种元素是三元素数组的就能考虑拆分数组了\n",
    "\n",
    "        diff = [0] * len(s)\n",
    "\n",
    "        for i in shifts:\n",
    "            '''\n",
    "            if i[2]: k = 1\n",
    "            else: k = -1\n",
    "            '''\n",
    "            # dir * 2 - 1\n",
    "            diff[i[0]] += i[2] * 2 - 1\n",
    "            if i[1] + 1 < len(s): diff[i[1] + 1] -= i[2] * 2 - 1\n",
    "\n",
    "        ans = ''\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if i > 0: diff[i] += diff[i - 1]\n",
    "            ans += chr(ord('a') + (ord(s[i]) - ord('a') + diff[i]) % 26)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            shifts[i] = (shifts[i] + shifts[i+1]) % 26\n",
    "        for i in range(n):\n",
    "            shifts[i] = (ord(s[i]) + shifts[i] - 97) % 26 + 97\n",
    "        return ''.join(map(chr, shifts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        for i in range(len(shifts)-2, -1, -1):\n",
    "            shifts[i] = (shifts[i] + shifts[i+1]) % 26\n",
    "        ans = []\n",
    "        for c, i in zip(s, shifts):\n",
    "            new = (ord(c) + i - 97) % 26 + 97\n",
    "            ans.append(chr(new))\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        shifts[-1]=shifts[-1]%26\n",
    "        for i in range(len(shifts)-2,-1,-1):\n",
    "            shifts[i]=(shifts[i]+shifts[i+1])%26\n",
    "        tmp=[]\n",
    "        maxnumber=ord('z')+1\n",
    "        for i in range(len(shifts)):\n",
    "            val=ord(s[i])+shifts[i]\n",
    "            if val>=maxnumber:\n",
    "                val-=26\n",
    "            tmp.append(chr(val))\n",
    "        return \"\".join(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import string\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        for i in range(len(shifts)-2, -1, -1):\n",
    "            shifts[i] += shifts[i+1]\n",
    "            shifts[i] %= 26\n",
    "        ans = ''\n",
    "        t = string.ascii_lowercase*2\n",
    "        print(shifts)\n",
    "        for i, c in enumerate(s):\n",
    "            ans += t[t.index(c)+shifts[i]%26]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        nsize = len(shifts)\n",
    "        ans = [s[0]] * nsize\n",
    "\n",
    "        for i in range(nsize - 1, -1, -1):\n",
    "            if i != nsize - 1:\n",
    "               shifts[i] += shifts[i + 1]\n",
    "\n",
    "            shifts[i] %= 26\n",
    "            ans[i] = ord(s[i]) + shifts[i]\n",
    "            if ans[i] > ord('z'):\n",
    "                ans[i] -= 26\n",
    "            ans[i] = chr(ans[i])\n",
    "\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        s = list(s)\n",
    "        n = len(shifts)\n",
    "        shifts.append(0)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            shifts[i] = (shifts[i] + shifts[i+1]) % 26\n",
    "            s[i] = chr((ord(s[i]) - ord(\"a\") + shifts[i]) % 26 + ord(\"a\"))\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(s)\n",
    "        shifts.append(0)\n",
    "        res = [''] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            shifts[i] = (shifts[i] + shifts[i+1]) % 26\n",
    "            res[i] = chr((ord(s[i]) - 97 + shifts[i]) % 26 + 97)\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shiftingLetters(self, S, shifts):\n",
    "        ans = []\n",
    "        X = sum(shifts) % 26\n",
    "        for i, c in enumerate(S):\n",
    "            index = ord(c) - ord('a')\n",
    "            ans.append(chr(ord('a') + (index + X) % 26))\n",
    "            X = (X - shifts[i]) % 26\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n, t = len(s), 0\n",
    "        s = list(s)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            t += shifts[i]\n",
    "            j = (ord(s[i]) - ord('a') + t) % 26\n",
    "            s[i] = ascii_lowercase[j]\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def shiftingLetters(self, S, shifts):\n",
    "        ans = []\n",
    "        X = sum(shifts) % 26\n",
    "        for i, c in enumerate(S):\n",
    "            index = ord(c) - ord('a')\n",
    "            ans.append(chr(ord('a') + (index + X) % 26))\n",
    "            X = (X - shifts[i]) % 26\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        res1 = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g', 7: 'h', 8: 'i', 9: 'j', 10: 'k', 11: 'l', 12: 'm',\n",
    "        13: 'n', 14: 'o', 15: 'p', 16: 'q', 17: 'r', 18: 's', 19: 't', 20: 'u', 21: 'v', 22: 'w', 23: 'x', 24: 'y',\n",
    "        25: 'z'}\n",
    "        res2 = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12,\n",
    "                'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24,\n",
    "                'z': 25}\n",
    "        ans = ''\n",
    "        n = len(s)\n",
    "        pre = 0\n",
    "        for idx in range(n - 1,-1,-1):\n",
    "            pre += shifts[idx]\n",
    "            shifts[idx] = pre % 26\n",
    "        for i in range(n):\n",
    "            temp = res1[(res2[s[i]] + shifts[i]) % 26]\n",
    "            ans += temp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = []\n",
    "        X = sum(shifts) % 26\n",
    "        for i, c in enumerate(s):\n",
    "            index = ord(c) - ord('a')\n",
    "            ans.append(chr(ord('a') + (index + X) % 26))\n",
    "            X = (X - shifts[i]) % 26\n",
    "\n",
    "        return \"\".join(ans)\n",
    "        ###########3\n",
    "        # final = \"\"\n",
    "        # # 算出来每个item需要的移位总数\n",
    "        # for i in range(len(shifts)):\n",
    "        #     shifts[i] = sum(shifts[i:]) % 26\n",
    "\n",
    "        # for idx,item in enumerate(s):\n",
    "        #     n_tmp = chr((ord(item)-97 +shifts[idx])%26 + 97)\n",
    "        #     final += n_tmp\n",
    "        # return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self,s, shifts):\n",
    "        for i in range(len(shifts) - 1, -1, -1):\n",
    "            if i != len(shifts) - 1:\n",
    "                shifts[i] += shifts[i + 1]\n",
    "            shifts[i] %= 26\n",
    "\n",
    "        shifted_s = \"\"\n",
    "        for i in range(len(s)):\n",
    "            shift = (ord(s[i]) - ord('a') + shifts[i]) % 26\n",
    "            shifted_s += chr(ord('a') + shift)\n",
    "\n",
    "        return shifted_s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = []\n",
    "        X = sum(shifts) % 26\n",
    "        for i, c in enumerate(s):\n",
    "            index = ord(c) - ord('a')\n",
    "            ans.append(chr(ord('a') + (index + X) % 26))\n",
    "            X = (X - shifts[i]) % 26\n",
    "\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        pshift = [None] * n\n",
    "        ans = 0\n",
    "        ssum = sum(shifts)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            pshift[i] = (ssum - ans) % 26\n",
    "            ans += shifts[i]\n",
    "            i += 1\n",
    "        ss = \"\"\n",
    "        for i,ch in enumerate(s):\n",
    "            m = ord(ch) + pshift[i]\n",
    "            if m > 122:\n",
    "                m -= 26\n",
    "            ss += chr(m)\n",
    "        \n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        s, ans, move = [x for x in s], [], 0\n",
    "        while s:\n",
    "            char = s.pop()\n",
    "            move = move + shifts.pop()\n",
    "            ans.append(chr(((ord(char) + move) - ord('a')) % 26 + ord('a')))\n",
    "        return ''.join(reversed(ans))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(s)\n",
    "        res = ''\n",
    "        from collections import deque\n",
    "        allshifts = deque()\n",
    "        t = 0\n",
    "        for i in shifts[::-1]:\n",
    "            t+=i\n",
    "            allshifts.insert(0, t) \n",
    "        table = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        for i, shift in enumerate(allshifts):\n",
    "            shift = shift % 26\n",
    "            index = (ord(s[i])-ord('a')+shift)%26\n",
    "            c = table[index]\n",
    "            res+=c\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(s)\n",
    "        d = [0] * (n + 1)\n",
    "        for i, c in enumerate(s):\n",
    "            v = ord(c) - ord('a')\n",
    "            d[i] += v\n",
    "            d[i + 1] -= v\n",
    "        for i, x in enumerate(shifts):\n",
    "            d[0] += x\n",
    "            d[i + 1] -= x\n",
    "        t = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            d[i] %= 26\n",
    "            ans.append(ascii_lowercase[d[i]])\n",
    "            d[i + 1] += d[i]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        l = []\n",
    "        base = ord('a')\n",
    "        for c in s:\n",
    "            l.append(ord(c)-base)\n",
    "        shift = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            shift += shifts[i]\n",
    "            l[i] = chr((l[i] + shift) % 26 + base)\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        l=len(shifts)\n",
    "        for i in range(l-2,-1,-1):\n",
    "            shifts[i]+=shifts[i+1]\n",
    "        ret = [\"\" for _ in range(l)]\n",
    "        for i in range(l):\n",
    "            ret[i]=chr((ord(s[i])-ord(\"a\")+shifts[i])%26+ord(\"a\"))\n",
    "        return \"\".join(ret)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ss = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',\n",
    "              'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n",
    "        s, num = list(s), sum(shifts)\n",
    "\n",
    "        for i in range(len(shifts)):\n",
    "            s[i] = ss[(num+ss.index(s[i])) % 26]\n",
    "            num -= shifts[i]\n",
    "\n",
    "        return \"\".join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(s)\n",
    "        table = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "        i2c_dic = {}\n",
    "        c2i_dic = {}\n",
    "        for i, c in enumerate(table):\n",
    "            i2c_dic[i] = c\n",
    "            c2i_dic[c] = i\n",
    "        ans = ''\n",
    "        ct = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ct += shifts[i]\n",
    "            c = s[i]\n",
    "            ci = c2i_dic[c] + ct\n",
    "            ans = i2c_dic[ci%26] + ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        total = sum(shifts)\n",
    "        n = len(s)\n",
    "        list_s = list(s)\n",
    "        for i in range(n):\n",
    "            val = (ord(list_s[i]) + total - ord('a')) % 26 + ord('a')\n",
    "            list_s[i] = chr(val)\n",
    "            total -= shifts[i]\n",
    "        return \"\".join(list_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        a = ord('a')\n",
    "        map = [chr(i +a) for i in range(26)]\n",
    "        \n",
    "        for i in range(len(shifts)-2,-1,-1):\n",
    "            shifts[i] += shifts[i+1]\n",
    "\n",
    "        s = list(s)\n",
    "        for i in range(len(s)):\n",
    "            old_idx = ord(s[i]) - a\n",
    "            new_idx = (old_idx + shifts[i]) % 26\n",
    "            s[i] = map[new_idx]\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        shift = 0\n",
    "        for i in range(len(shifts)-1, -1, -1):\n",
    "            shift += shifts[i]\n",
    "            index = (alphabet.index(s[i]) + shift) % 26\n",
    "            s = s[:i] + alphabet[index] + s[i+1:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        res = \"\"\n",
    "        shift_counts = 0\n",
    "\n",
    "        for i in range(len(shifts)):\n",
    "            shift_counts += shifts[len(shifts)-1-i]\n",
    "            res = chr((ord(s[len(shifts)-1-i]) - ord('a') + shift_counts) % 26 + ord('a')) + res\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "\n",
    "        n = len(shifts)\n",
    "\n",
    "        suffix = [0]*n\n",
    "\n",
    "        suffix[-1] = shifts[-1]\n",
    "\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suffix[i] = suffix[i+1] + shifts[i]\n",
    "        \n",
    "        res = ''\n",
    "        for i in range(n-1,-1,-1):\n",
    "            c = s[i]\n",
    "            index = ord(c) - 97 + suffix[i]\n",
    "            index %= 26\n",
    "            res =  chr(index+97) + res \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            shifts[i] += shifts[i + 1]\n",
    "        # print(shifts)\n",
    "        res = \"\"\n",
    "        for c, shift in zip(s, shifts):\n",
    "            i = ord(c) - ord('a')\n",
    "            j = (i + shift) % 26\n",
    "            res += chr(ord('a') + j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        lsh = []\n",
    "        for i in shifts[::-1]:\n",
    "            if lsh == []:\n",
    "                lsh.append(i)\n",
    "            else:\n",
    "                lsh.append(lsh[-1]+i)\n",
    "        lc = []\n",
    "        for c, i in zip(s, lsh[::-1]):\n",
    "            lc.append(chr((ord(c)-97+i)%26+97))\n",
    "        return ''.join(lc)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        res = \"\"\n",
    "        for i in range(n-2, -1, -1):\n",
    "            shifts[i] = (shifts[i] + shifts[i+1])\n",
    "        for j in range(n):\n",
    "            code = ord(s[j]) + (shifts[j] % 26)\n",
    "            if code > ord(\"z\"):\n",
    "                code -= 26\n",
    "            res = res + chr(code)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        s1 = [0 for _ in range(len(s))]\n",
    "        r = ''\n",
    "        #print(sh)\n",
    "        for i in range(len(shifts)-2 , -1 , -1):\n",
    "            shifts[i] += shifts[i+1]\n",
    "\n",
    "        #print(s1)\n",
    "        for k in range(len(s)):\n",
    "            a = ord(s[k]) + shifts[k]%26\n",
    "            if a > 122:\n",
    "                a -= 26\n",
    "            r += chr(a)\n",
    "        #print('\\\"'+ r + '\\\"')\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        res = []\n",
    "        X = sum(shifts)\n",
    "        for i in range(len(s)):\n",
    "            res.append(chr(ord('a') + (ord(s[i]) - ord('a') + X) % 26))\n",
    "            X = X - shifts[i]\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        shifts.reverse()\n",
    "        for i, n in enumerate(accumulate(shifts)):\n",
    "            shifts[i] = n\n",
    "        shifts.reverse()\n",
    "        ans = []\n",
    "        for c, i in zip(s, shifts):\n",
    "            new = ord(c) + i\n",
    "            new -= (new - 97) // 26 * 26\n",
    "            ans.append(chr(new))\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        res = []\n",
    "        X = sum(shifts) % 26\n",
    "        for i, ch in enumerate(s):\n",
    "            index = ord(ch) - ord('a')\n",
    "            res.append(chr(ord('a') + (index + X) % 26))\n",
    "            X = (X - shifts[i]) % 26\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        for i in range(len(shifts) - 2, -1, -1):\n",
    "            shifts[i] += shifts[i + 1]\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            res.append(chr((ord(s[i]) - ord(\"a\") + shifts[i]) % 26 + ord(\"a\")))\n",
    "        return \"\".join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, S: str, shifts: List[int]) -> str:\n",
    "        res=[]\n",
    "        total=sum(shifts)\n",
    "        for i in range(len(S)):\n",
    "            x=(ord(S[i])+total-97)%26\n",
    "            res.append(chr(x+97))   \n",
    "            total-=shifts[i]\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(s)\n",
    "        cur = 0\n",
    "        ans = [None] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur = (cur + shifts[i]) % 26\n",
    "            ans[i] = chr(97 + (ord(s[i]) - 97 + cur) % 26)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "w=\"abcdefghijklmnopqrstuvwxyz\"\r\n",
    "class Solution:\r\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\r\n",
    "\r\n",
    "        res=['']*len(s)\r\n",
    "        al=0\r\n",
    "        for i in range(len(s)-1,-1,-1):\r\n",
    "            al+=shifts[i]\r\n",
    "            res[i]=w[(ord(s[i])-97+al)%26]\r\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = ''\n",
    "        total_shift = 0\n",
    "        for i in reversed(range(len(s))):\n",
    "            total_shift += shifts[i]%26\n",
    "            total_shift %= 26\n",
    "            index = ord(s[i])-ord('a')\n",
    "            index += total_shift\n",
    "            index %= 26\n",
    "            ans += chr(index+ord('a'))\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        for i in range(len(shifts) - 2, -1, -1):\n",
    "            shifts[i] += shifts[i + 1]\n",
    "        ans = ''\n",
    "        for i in range(len(s)):\n",
    "            ans += chr((ord(s[i]) - ord('a') + shifts[i]) % 26 + ord('a'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = ''\n",
    "        for i in range(len(shifts) - 2, -1, -1):\n",
    "            shifts[i] += shifts[i + 1]\n",
    "        for i in range(len(s)):\n",
    "            ans += chr((ord(s[i]) - ord('a') + shifts[i]) % 26 + ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        total_sum = sum(shifts)\n",
    "        \n",
    "        res = []\n",
    "        for idx, char in enumerate(s):\n",
    "            this_char = chr((ord(char) - ord('a') + total_sum) % 26 + ord('a'))\n",
    "            res.append(this_char)\n",
    "\n",
    "            total_sum = total_sum - shifts[idx]\n",
    "\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\r\n",
    "        ans = []\r\n",
    "        n = len(s)\r\n",
    "        for i, alpha in zip(range(n-1,-1,-1), s[::-1]):\r\n",
    "            if i != n - 1:\r\n",
    "                shifts[i] += shifts[i+1]\r\n",
    "            ans.append(chr((ord(alpha) - ord('a') + shifts[i]) % 26 + ord('a')))\r\n",
    "        return ''.join(ans)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = ''\n",
    "        total = sum(shifts)\n",
    "        for i in range(len(s)):\n",
    "            ans += chr((ord(s[i]) - ord('a') + total) % 26 + ord('a'))\n",
    "            total -= shifts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "\n",
    "        N=len(shifts)\n",
    "        presum=[0 for i in range(0, N)]\n",
    "        presum[N-1]=shifts[N-1]\n",
    "        for i in range(N-2, -1, -1):\n",
    "            presum[i]=presum[i+1]+shifts[i]\n",
    "        # print(presum)\n",
    "        res=\"\"\n",
    "        for i in range(len(s)):\n",
    "            index=ord(s[i])-ord('a')\n",
    "            res+=chr((index+presum[i])%26+ord('a'))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        total_sum = sum(shifts)\n",
    "\n",
    "        total_shifts = [total_sum]\n",
    "\n",
    "        for i in range(1, len(shifts)):\n",
    "            total_sum = total_sum - shifts[i-1] \n",
    "            total_shifts.append(total_sum)\n",
    "\n",
    "        \n",
    "        res = ''\n",
    "        for idx in range(len(s)):\n",
    "            res = res + chr((ord(s[idx]) - ord('a') + total_shifts[idx]) % 26 + ord('a'))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        suffixSum = [0] * n\n",
    "        suffixSum[-1] = shifts[-1]\n",
    "        for i in range(len(shifts) - 2, -1, -1):\n",
    "            suffixSum[i] = suffixSum[i + 1] + shifts[i]\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            index = ord(s[i]) - ord(\"a\")\n",
    "            res.append(chr(ord(\"a\") + (suffixSum[i] + index) % 26))\n",
    "        return \"\".join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "w=\"abcdefghijklmnopqrstuvwxyz\"\r\n",
    "class Solution:\r\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\r\n",
    "        s=map(lambda x:ord(x)-ord('a'),list(s))\r\n",
    "        s=list(s)\r\n",
    "        res=''\r\n",
    "        tmp=0\r\n",
    "        for i in range(len(s)-1,-1,-1):\r\n",
    "            tmp+=shifts[i]\r\n",
    "            res=w[(s[i]+tmp)%26]+res\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\r\n",
    "        pre_sums=[0]*len(s)\r\n",
    "        pre_sums[-1]=shifts[-1]\r\n",
    "        for i in range(len(s)-2,-1,-1):\r\n",
    "            pre_sums[i]=pre_sums[i+1]+shifts[i]\r\n",
    "\r\n",
    "        ret=['']*len(s)\r\n",
    "        ord_a=ord('a')\r\n",
    "        for i,shift in enumerate(pre_sums):\r\n",
    "            \r\n",
    "            ret[i]=chr((ord(s[i])+shift-ord_a)%26+ord_a)\r\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        suffix_sum = []\n",
    "\n",
    "        sum = 0\n",
    "        for i in shifts[::-1]:\n",
    "            suffix_sum.append(sum + i)\n",
    "            sum = (sum + i) % 26\n",
    "\n",
    "        suffix_sum.reverse()\n",
    "\n",
    "        res = \"\"\n",
    "        for idx, letter in enumerate(s):\n",
    "            res+=chr((ord(letter)-ord('a')+suffix_sum[idx])%26 + ord('a'))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        return ''.join(chr(97 + (ord(c) - 97 + i) % 26)  for c, i in zip(s, list(accumulate(shifts[::-1]))[::-1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        pre = [0]\n",
    "        for i in range(len(shifts)-1, -1, -1):\n",
    "            pre.append(shifts[i]+pre[-1]) \n",
    "        pre = pre[::-1][:-1]\n",
    "\n",
    "        strs = list(s)\n",
    "        for i in range(len(strs)):\n",
    "            shift = (ord(strs[i])-ord('a')+pre[i])%26\n",
    "            strs[i] = chr(shift + ord('a'))\n",
    "        return ''.join(strs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        n = len(s)\n",
    "        c = sum(shifts)\n",
    "        res = [''] * n\n",
    "        for i in range(n):\n",
    "            d = c % 26\n",
    "            v = ord(s[i]) + c % 26\n",
    "            if v > ord('z'):\n",
    "                v = v - ord('z') - 1 + ord('a')\n",
    "            res.append(chr(v))\n",
    "            c -= shifts[i]\n",
    "        return ''.join(res)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        n = len(shifts)\n",
    "        suffix_sum = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i == n - 1:\n",
    "                suffix_sum[i] = shifts[i]\n",
    "            else:\n",
    "                suffix_sum[i] = suffix_sum[i + 1] + shifts[i]\n",
    "        shifts_real = [shift % 26 for shift in suffix_sum]\n",
    "        ans = []\n",
    "        for c, shift in zip(s, shifts_real):\n",
    "            k = ord(c) + shift\n",
    "            if k > ord('z'):\n",
    "                k -= 26\n",
    "            ans.append(chr(k))\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def shiftingLetters(self, s , shifts):\n",
    "    st, end = ord('a'), ord('z')\n",
    "    ans = ''\n",
    "    n = len(shifts)    \n",
    "    per_sum = [0] * (n + 1)\n",
    "    for i in range(1, n + 1):\n",
    "      per_sum[i] += per_sum[i - 1] + shifts[-i]\n",
    "    per_sum[1:] = per_sum[1:][::-1]\n",
    "    # print(per_sum)\n",
    "    for i, ch in enumerate(s):\n",
    "      t = ord(ch) + (per_sum[i + 1] % 26)\n",
    "      if t > end:\n",
    "        t = (t - end) - 1 + st\n",
    "      ans += chr(t)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        d = list(accumulate(shifts[::-1]))[::-1]\n",
    "        A = [ord(ch) + x - 97 for ch,x in zip(s,d)] \n",
    "        return ''.join(chr(x%26+97) for x in A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        # use differential array to solve the problem \n",
    "        # arr[i] = arr[i-1] + diff[i]\n",
    "        # to increase value in arr[i...j] by k, diff[i] += k, diff[j+1] -= k \n",
    "        n = len(s)\n",
    "        diff = [0]*n\n",
    "        for i in range(n):\n",
    "            x = shifts[i]\n",
    "            # shift arr[0..i] by x \n",
    "            diff[0] += x \n",
    "            if i + 1 < n:\n",
    "                diff[i+1] -= x \n",
    "        # generate arr \n",
    "        arr = [0]*n\n",
    "        arr[0] = diff[0]\n",
    "        for i in range(1,n):\n",
    "            arr[i] = arr[i-1] + diff[i]\n",
    "        # assemble result \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            newChar = chr( (ord(c) - ord('a') + 26 + arr[i])%26 + ord('a'))\n",
    "            res.append(newChar)\n",
    "        return ''.join(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = ''\n",
    "        for i in range(len(shifts) - 2, -1, -1):\n",
    "            shifts[i] += shifts[i + 1]\n",
    "        print(shifts)\n",
    "        for c, i in zip(s, shifts):\n",
    "            ans += chr((ord(c) - ord('a') + i) % 26 + ord('a'))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, S: str, shifts: List[int]) -> str:\n",
    "        import numpy as np\n",
    "        result = \"\"\n",
    "        for i in range(1,len(shifts)+1):\n",
    "            if i == 1 :\n",
    "                shifts[-i] = shifts[-i]\n",
    "            else : \n",
    "                shifts[-i] += shifts[-i+1] \n",
    "        for j in range(0,len(shifts)):\n",
    "            result += chr( ord('a')+ (ord(S[j]) - ord('a') + shifts[j])%26 )\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        record = [0]\n",
    "        n = len(s)\n",
    "        for each in shifts:\n",
    "            record.append(each+record[-1])\n",
    "        print(record)\n",
    "        ans = ''\n",
    "        res = [0]*n\n",
    "        for i in range(n):\n",
    "            res[i] = record[-1]-record[i]\n",
    "        print(res)\n",
    "        for i in range(n):\n",
    "            diff = res[i]%26\n",
    "            ch = s[i]\n",
    "            ans += chr((ord(ch)-ord('a')+diff)%26+ord('a'))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, S: str, shifts: List[int]) -> str:\n",
    "        import numpy as np\n",
    "        result = \"\"\n",
    "        for i in range(1,len(shifts)+1):\n",
    "            if i == 1 :\n",
    "                shifts[-i] = shifts[-i]\n",
    "            else : \n",
    "                shifts[-i] += shifts[-i+1] \n",
    "        for j in range(0,len(shifts)):\n",
    "            result += chr( ord('a')+ (ord(S[j]) - ord('a') + shifts[j])%26 )\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shiftingLetters(self, s: str, shifts: List[int]) -> str:\n",
    "        ans = []\n",
    "        acc = 0\n",
    "        for c,t in list(zip(s,shifts))[::-1]:\n",
    "            acc += t\n",
    "            ans.append(chr(ord('a') + (ord(c)-ord('a')+acc)%26))\n",
    "        return ''.join(ans[::-1])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
